package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/merge-intervals/">合并区间(Merge Intervals)</a>
 * <p>以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 *      输出：[[1,6],[8,10],[15,18]]
 *      解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 *
 * 示例 2：
 *      输入：intervals = [[1,4],[4,5]]
 *      输出：[[1,5]]
 *      解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 *     </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= intervals.length <= 10^4</li>
 *         <li>intervals[i].length == 2</li>
 *         <li>0 <= starti <= endi <= 10^4</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/16 18:38
 */
public class LC0056MergeIntervals_M {

    static class Solution {
        public int[][] merge(int[][] intervals) {
            Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
            int length = intervals.length;
            List<int[]> resultList = new ArrayList<>();
            for (int i = 0; i < length - 1; i++) {
                int currStart = intervals[i][0];
                int currEnd = intervals[i][1];
                int nextStart = intervals[i + 1][0];
                int nextEnd = intervals[i + 1][1];
                // 无交集
                if (currEnd < nextStart) {
                    resultList.add(new int[]{currStart, currEnd});
                }
                // 有交集
                else {
                    // 包含的情况。curr包含next
                    if (currStart <= nextStart && currEnd >= nextEnd) {
                        intervals[i + 1][0] = currStart;
                        intervals[i + 1][1] = currEnd;
                    }
                    // 包含的情况。next包含curr
                    else if (currStart >= nextStart && currEnd <= nextEnd) {
                        intervals[i + 1][0] = nextStart;
                        intervals[i + 1][1] = nextEnd;
                    }
                    // 相交的情况
                    else {
                        intervals[i + 1][0] = currStart;
                        intervals[i + 1][1] = nextEnd;
                    }
                }
            }
            resultList.add(new int[]{intervals[length - 1][0], intervals[length - 1][1]});
            // 将List转为数组
            return resultList.toArray(new int[resultList.size()][2]);
        }

        public int[][] merge2(int[][] intervals) {
            Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
            List<int[]> merged = new ArrayList<>();
            for (int[] interval : intervals) {
                // merged.get(merged.size() - 1)：前一组
                // 如果当前组的start > 前一组的 end。出现新的组
                if (merged.size() == 0 || interval[0] > merged.get(merged.size() - 1)[1]) {
                    merged.add(interval);
                } else {
                    merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
                }
            }
            // 将List转为数组
            return merged.toArray(new int[merged.size()][2]);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] merge;
        //merge = solution.merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}});
        //for (int i = 0; i < merge.length; i++) {
        //    System.out.print("(" + merge[i][0] + "," + merge[i][1] + ")  ");
        //    if (i == merge.length - 1) {
        //        System.out.println();
        //    }
        //}
        //merge = solution.merge(new int[][]{{1, 4}, {4, 5}});
        //for (int i = 0; i < merge.length; i++) {
        //    System.out.print("(" + merge[i][0] + "," + merge[i][1] + ")  ");
        //    if (i == merge.length - 1) {
        //        System.out.println();
        //    }
        //}

        //merge = solution.merge(new int[][]{{1, 4}, {0, 4}});
        //for (int i = 0; i < merge.length; i++) {
        //    System.out.print("(" + merge[i][0] + "," + merge[i][1] + ")  ");
        //    if (i == merge.length - 1) {
        //        System.out.println();
        //    }
        //}
        //merge = solution.merge(new int[][]{{1, 4}, {0, 1}});
        //for (int i = 0; i < merge.length; i++) {
        //    System.out.print("(" + merge[i][0] + "," + merge[i][1] + ")  ");
        //    if (i == merge.length - 1) {
        //        System.out.println();
        //    }
        //}
        //merge = solution.merge(new int[][]{{1, 4}, {0, 0}});
        //for (int i = 0; i < merge.length; i++) {
        //    System.out.print("(" + merge[i][0] + "," + merge[i][1] + ")  ");
        //    if (i == merge.length - 1) {
        //        System.out.println();
        //    }
        //}

        merge = solution.merge(new int[][]{{2, 3}, {4, 5}, {1, 7}});
        for (int i = 0; i < merge.length; i++) {
            System.out.print("(" + merge[i][0] + "," + merge[i][1] + ")  ");
            if (i == merge.length - 1) {
                System.out.println();
            }
        }

    }
}
